package algorthm.systemTraning.heap;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.PriorityBlockingQueue;

/**
 * @className: MyHeap
 * @Description:
 * @Author: wangyifei
 * @Date: 2022/9/29 14:53
 */
public class MyHeap {
    private static Logger logger = LoggerFactory.getLogger(MyHeap.class);
    public static class Heap{
        private int capacity ;
        private int[] heap ;
        private int heapSize ;
        public Heap(int limit){
            this.capacity = limit ;
            this.heap = new int[limit];
            heapSize = 0 ;
        }
        public void push(int i){
            if(i<0){
                throw new RuntimeException("越界");
            }
            if(heapSize >= capacity ){
                throw new RuntimeException("越界");
            }
            insertHeap(heap , i , heapSize++);
        }
        public boolean isEmpty(){
            return heapSize == 0;
        }
        public int pop(){
            if(heapSize == 0){
                throw new RuntimeException("越界");
            }
            int ans = heap[0] ;
            heapfy(heap , 0 , --heapSize);
            return ans ;
        }
        public void swap(int[] array , int from , int to){
            if(from == to){
                return ;
            }
            array[from] = array[from]^array[to] ;
            array[to] = array[from]^array[to] ;
            array[from] = array[from]^array[to] ;
        }
        public void insertHeap(int[] heap , int target , int insertIdx){
            int root = 0 ;
            heap[insertIdx] = target ;
            while(insertIdx >= 0){
                root = (insertIdx - 1)/2;
                if(heap[root] < heap[insertIdx]){
                    swap(heap , root , insertIdx);
                    insertIdx = root ;
                }else{
                    break;
                }
            }
        }
        public void heapfy(int[] heap , int root , int leaf){
            swap(heap , root , leaf);
            // 计算左子树的位置
            int left = 2*root + 1 ;
            int max = 0 ;
            while(left < leaf){
                max = (left+1 < leaf && heap[left] < heap[left + 1])? left + 1 : left ;
                max = (heap[max] > heap[root])? max:root;
                // root 位置上，root 节点大于了叶子节点，不需要再往下沉了
                if(root == max){
                    break ;
                }
                // 如果最大的子节点比 root 节点大，则进行交换
                swap(heap , root , max);
                // 下一个需要比较的 root 节点变成了 max
                root = max ;
                left = 2*root + 1;
            }
        }
    }
    public static int[] randomArray(int range , int size){
        Random r = new Random();
        int s = r.nextInt(size) + 1;
        int[] ans = new int[s];
        for(int i = 0 ; i < s ; i++){
            ans[i] = r.nextInt(range);
        }
        return ans ;
    }
    public static void compare(int range , int size , int times){
        Heap h = null ;
        PriorityBlockingQueue<Integer> queue = null ;
        int[] array = null ;
        Random r = new Random();
        for(int i = 0 ; i < times ; i++){
            array = randomArray(range , size);
            h = new Heap(array.length);
            queue = new PriorityBlockingQueue<Integer>(array.length , (i1 , i2)-> {
                return i2 - i1;
            });
            for(int e : array){
                h.push(e);
                queue.put(e);
            }
            while(!h.isEmpty()&&!queue.isEmpty()){
                if(h.pop() != queue.poll()){
                    System.out.println("1Oops , array is :" + Arrays.toString(array));
                }
            }
            if(!h.isEmpty() || !queue.isEmpty()){
                System.out.println("2Oops");
            }
        }
    }
    public static void main(String[] args){
        compare(100 , 43 , 1098870);
//        int[] array = {68, 37, 80, 41, 12, 77, 43, 41, 92, 0, 20, 15};
//        Heap h = new Heap(array.length);
//        PriorityBlockingQueue<Integer> queue = new PriorityBlockingQueue(array.length);
//        for(int i : array){
//            h.push(i);
//            queue.put(i);
//        }
//        while(!h.isEmpty()){
//            System.out.println(h.pop());
//        }
//        while(!queue.isEmpty()){
//           System.out.println(queue.poll());
//        }
    }
}
